package 链表;

public class No25K个一组翻转链表 {

    /**
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * <p>
     * 示例：
     * 给你这个链表：1->2->3->4->5
     * 当 k = 2 时，应当返回: 2->1->4->3->5
     * 当 k = 3 时，应当返回: 3->2->1->4->5
     */

    public static ListNode reverseKGroupGood(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;//前驱节点
        ListNode end = dummy;//末尾节点


        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++)
                end = end.next;
            if (end == null)
                break;

            ListNode start = pre.next;//记录开始节点
            ListNode next = end.next;//记录后驱节点
            end.next = null;//截断

            pre.next = reverseGood(start);//截断后再放进去
            start.next = next;//翻转后拼接后驱节点

            pre = start;//重置前驱节点(只要一个前驱就可以了)
            end = pre;//重置末尾节点
        }
        return dummy.next;
    }

    private static ListNode reverseGood(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    public static ListNode reverseK(ListNode head, int k) {

        //一段一段的翻转
        ListNode listNode = new ListNode();
        listNode.next = head;

        ListNode pre = listNode;//前驱节点
        ListNode cur = listNode;//当前节点

        while (cur.next != null) {

            for (int i = 0; i < k && cur != null; i++) {
                cur = cur.next;
            }

            if (cur == null)
                break;

            ListNode startNode = pre.next;//开始节点
            ListNode readNode = cur.next;//后驱节点

            cur.next = null;//截断

            //翻转后返回的是链表头
            pre.next = reverse(startNode);//翻转+拼接前驱
            startNode.next = readNode;//翻转后末尾就是startNode,拼接后驱

            //维护
            pre = startNode;//前驱
            cur = pre;//拼接

        }

        return listNode.next;

    }

    private static ListNode reverse(ListNode head) {
        ListNode listNode = new ListNode();
        listNode.next = head;
        ListNode pre = listNode;
        ListNode next;
        ListNode cur = listNode.next;

        while (cur != null) {

            next = cur.next;

            cur.next = pre;

            pre = cur;

            cur = next;

        }

        return pre;
    }

    /**
     * 1.父函数吃什么?(包含return什么,return上去的怎么处理?)
     * return回来的是翻转好的链表,父吃点翻转好的链表
     * 2.递归的具体操作(根据题目的自定义问题)
     * 在里面翻转好链表,然后return自己,return之前自己也需要吃子链表
     */
    public static ListNode reverseKDG(ListNode head, int k) {
        if (k == 0 || k == 1 || head == null)
            return head;
        ListNode dg = DG(head, k);
        return dg;
    }

    private static ListNode DG(ListNode head, int k) {
        int index = 0;
        ListNode listNode = new ListNode();
        listNode.next = head;
        ListNode cur = listNode;
        while (index < k && cur != null) {
            cur = cur.next;
            if (cur != null)
                index++;
        }
        if (index == k) {
            ListNode next = cur.next;//记录后驱
            cur.next = null;//截断
            //返回翻转好的链表
            ListNode reverse = reverse(listNode.next);

            listNode.next.next = DG(next, k);
            return reverse;
        } else {
            return listNode.next;
        }
    }

    /**
     * 回顾
     * todo 用 dump更新一下好吗?
     */
    public ListNode reverseListNodeByGroup(ListNode listNode, int k) {


        ListNode firstNode = listNode;
        ListNode result = null;
        ListNode lastEndNode = null;
        ListNode cur = listNode;

        while (cur != null) {

            int count = k;
            while (count > 1 && cur != null) {
                cur = cur.next;
                count--;
            }

            if (cur == null && count >= 1) {
                // 保持原序
                if (lastEndNode != null) {
                    lastEndNode.next = firstNode;
                }
                break;
            }

            if (result == null) {
                result = cur;
            }

            ListNode nextNode = cur.next;
            cur.next = null;
            // 翻转, cur是头节点
            this.reverseListNode(firstNode);
            if (lastEndNode != null) {
                lastEndNode.next = cur;
            }
            // 更新lastEndNode
            lastEndNode = firstNode;
            // 更新firstNode
            firstNode = nextNode;
            // 更新cur
            cur = nextNode;

        }

        return result;
    }

    /**
     * 反转链表
     * A -> B -> C -> D -> E -> F
     * D -> C -> B -> A -> F -> E
     */
    private ListNode reverseListNode(ListNode listNode) {

        ListNode lastNode = null;
        ListNode cur = listNode;

        while (cur != null) {

            // 记录
            ListNode nextNode = cur.next;
            // 翻转
            cur.next = lastNode;
            // 记录
            lastNode = cur;
            // 遍历
            cur = nextNode;

        }

        return lastNode;
    }


    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5};
        ListNode listNode = ListNode.createListNode(arr);
//        ListNode result1 = reverseKDG(listNode, 6);
//        ListNode.printListNode(result1);
//        System.out.println();
        No25K个一组翻转链表 n = new No25K个一组翻转链表();
        ListNode result2 = n.reverseListNodeByGroup(listNode, 3);
        ListNode.printListNode(result2);
    }

}
